package 二叉树的层序遍历II;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import 相同的树.TreeNode;

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        //创建二维数组
        List<List<Integer>> ret = new ArrayList<>();
        //树为空树直接返回
        if (root == null){
            return ret;
        }
        //创建队列,用来存放树中结点
        Queue<TreeNode> queue = new LinkedList<>();
        //先将根结点入队列
        queue.offer(root);
        //队列不为空说明树中还有结点没有存入二维数组中
        while (!queue.isEmpty()){
            //size用来记录这层数组要存放元素个数
            int size = queue.size();
            //创建一维数组来存放这层元素
            List<Integer> list = new ArrayList<>();
            //size不为0说明这层元素没有存放完
            while (size != 0){
                //tmp用来接收队首元素
                TreeNode tmp = queue.poll();
                //出队,size减1
                size--;
                //将元素tmp存入数组中
                list.add(tmp.val);
                //将tmp的左右子树根结点入队列
                if (tmp.left != null){
                    queue.offer(tmp.left);
                }
                if (tmp.right != null){
                    queue.offer(tmp.right);
                }
            }
            //将一维数组头插到二维数组中,保证从最后一层开始遍历
            ret.add(0,list);
        }
        //返回二维数组起始地址
        return ret;
    }
}